<DOCTYPE html>
  <html lang="en">

  <head charset="UTF-8">
    <title></title>
  </head>

  <body>
    <script type="text/javascript" src="队列结构算法.js"></script>
    <script type="text/javascript" src="字典算法.js"></script>
    <script>
      function Graph() {
        let vertexes = new Queue();
        let edges = new Dictionary();
        this.length = 0;

        Graph.prototype.has = key => {
          if (edges.has(key)) {
            return true
          }
          return null
        }

        Graph.prototype.add = key => {
          if (this.has(key)) {
            return false
          }
          vertexes.enqueue(key);
          edges.set(key, [])
          this.length++;
        }

        Graph.prototype.addEdge = (keyOne, keyTwo) => {
          if (this.has(keyOne) == null && this.has(keyTwo) == null) return false
          for (let i = 0; i < this.edges[keyOne].length; i++) {
            if (this.edges[keyOne][i] == keyTwo) {
              return false
            }
          }
          this.edges[keyOne].push(keyTwo);
          this.edges[keyTwo].push(keyOne);
        }

        Graph.prototype.toString = () => {
          if (this.length == 0) return null
          let result = ''
          for (let i = 0; i < this.edges.size(); i++) {
            result += this.edges.keyShow()[i] + '->' + this.edges.ValueShow()[i]
          }
          return result
        }

        Graph.prototype.remove = key => {
          if (this.length == 0) return null
          if (this.has(key) == null) return null
          for (let i = 0; i < this.vertexes.size(); i++) {
            if (this.vertexes.listShow()[i] == key) {
              this.vertexes.listShow().splice(i, 1)
              break
            }
          }
          this.edges.remove(key);
          this.length--;
        }

        //遍历
        //初始化节点状态
        Graph.prototype.inIt = () => {
          if (this.length == 0) return false
          let list = new Queue();
          for (let i = 0; i < this.vertexes.size(); i++) {
            this.list.enqueue(this.vertexes.listShow()[i])
          }
          for (let i = 0; i < this.list.size(); i++) {
            this.list.listShow()[i] = 'white';
          }
          return list
        }

        //广度优先遍历 bfs
        Graph.prototype.bfs = key => {
          if (this.has(key) == null) return null
          let whiteQueue = this.inIt();
          let grayQueue = new Queue();
          let blackQueue = new Queue();
          for (let i = 0; i < this.whiteQueue.size(); i++) {
            if (key == whiteQueue.listShow()[i]) {
              whiteQueue.splice(i, 1)
            }
          }
          key = "gray";
          grayQueue.enqueue(key);
          while (blackQueue.size() != this.length) {
            for (let i = 0; i < this.edges[grayQueue.listShow()[0]].length; i++) {
              for (let j = 0; j < whiteQueue.size(); j++) {
                if (whiteQueue.listShow()[j] == this.edges[grayQueue.listShow()[0]][i]) {
                  whiteQueue.listShow()[j] == 'gray';
                  grayQueue.enqueue(whiteQueue.listShow()[j])
                  whiteQueue.splice(j, 1)
                }
              }
            }
            let temp = grayQueue.dequeue();
            temp = 'black';
            blackQueue.enqueue(temp)
          }
          return blackQueue.listShow()
        }

        //深度优先遍历 dfs
        Graph.prototype.dfs = key => {
          let whiteQueue = this.inIt();
          let result = this.dfsVisit(key, whiteQueue);
          return result.split('');
        }

        Graph.prototype.dfsVisit = (key, queue) => {
          if (queue[key] == "white") {
            queue[key] = "gray"
            let result = ''
            result += queue[key]
            for (let i = 0; i < this.edges[key].length; i++) {
              result += this.dfsVisit(this.edges[key][i], queue)
            }
            queue[key] = "black"
            return result
          }
        }
      }

      let graph = new Graph();
      let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
      for (let i = 0; i < myVertexes.length; i++) {
        graph.add(myVertexes[i]);
      }
      graph.addEdge('A', 'B')
      graph.addEdge('A', 'C')
      graph.addEdge('A', 'D')
      graph.addEdge('C', 'D')
      graph.addEdge('C', 'G')
      graph.addEdge('D', 'G')
      graph.addEdge('D', 'H')
      graph.addEdge('B', 'E')
      graph.addEdge('B', 'F')
      graph.addEdge('E', 'I')
      console.log(graph.dfs());
    </script>
  </body>

  </html>